Asynchronous Transfer Mode (ATM) technology is being developed to support multi-service high-speed communication networks. An important component of such a technology is a policing or usage parameter control mechanism to ensure that users stay within negotiated usage guidelines when communicating over the network. The leaky bucket is a well-known policing mechanism which is widely accepted due to its inherent simplicity.
The simplest version of a leaky bucket policing mechanism has two parameters--the drain rate d which corresponds roughly to the rate at which cells are let into the leaky bucket and the maximum token pool size b which generally represents the maximum number of cells that can be handled by the leaky bucket at a given time. A third parameter, the measurement interval T, is often specified but has no direct impact on the performance of the leaky bucket.
As would be understood by a person skilled in the art, the maximum burst size allowed by the leaky bucket is larger than the token pool size by an amount which depends on the token pool size, drain rate, access line rate and the peak cell removal rate. For practical purposes, however, this distinction will be ignored in the instant discussion. In general, the leaky bucket operates as follows: every 1/d time units the number of tokens is incremented by 1, up to the maximum limit b. When a cell arrives to be transmitted, and a token is available, the cell is accepted by the leaky bucket and the number of tokens is decremented by 1. If a token is not available, the cell is discarded--thus the name "leaky bucket".
An equivalent alternate description of the leaky bucket includes a counter which counts the number of cell arrivals instead of accumulated tokens. Whenever a cell arrives and the cell count is less than the limit b, the cell count is incremented by 1 and the cell is allowed in. If the cell count is b, the cell is discarded. Every d.sup.-1 time units the cell count is decremented by 1.
There are various other generalizations of the leaky bucket mechanism found in the prior art. For example, the leaky bucket may contain a shaping buffer for incoming cells. Now, if a token is not immediately available, the cell is stored in the shaping buffer. The cell is then only discarded if the shaping buffer is full. Instead of being discarded, cells could also be tagged and let into the network at a lower priority or could be queued and other cells from the head of the queue tagged and let into the network.
Another type of leaky bucket mechanism found in the prior art is the adaptive leaky bucket. The adaptive leaky bucket discards cells only if no tokens are available and the measured load on the transmission link is above a prescribed threshold. Still another version of the leaky bucket mechanism, the jumping leaky bucket, works over short fixed time intervals called windows. The token counter is incremented by a fixed amount of tokens and decremented by the number of cells which arrived in the previous window. In addition, a leaky bucket with memory may accumulate information about discarded cells by letting the token counter dip below zero.
As mentioned, a main advantage of the leaky bucket is that it is relatively easy to implement. The leaky bucket, however, also has some significant disadvantages, a first being that the leaky bucket control mechanism may not be adequate for the typical bursty behavior of users in an ATM network. In addition, it is usually difficult to directly relate parameters of a leaky bucket to user traffic characteristics. That is, the two leaky bucket parameters, b and d, allow a wide range of user behavior and the network has no way of knowing how a user will behave. In order to protect itself and other users, the network may need to assume the worst case behavior allowed by the traffic parameters.
For example, it is traditionally believed that the nearly-worst case behavior for the traffic parameters in the leaky bucket is: ON-OFF with the ON period generating b cells at the access line speed every bd.sup.-1 time units. The ON-OFF behavior, however, is not always the worst case behavior as has been shown. In fact, assuming the worst case behavior can be quite conservative. For instance, the single limit b on the token pool size means that b must correspond to the largest burst size to be allowed in and, consequently, the leaky bucket can be overdimensioned.
One motivation for considering enhancements to the leaky bucket mechanism, as can be seen above, is that the single limit on the token pool size is too confining. For example, consider an illustration of network usage, where a user wants one in four bursts to be up to 400 cells and the other three bursts to be less than 200 cells.
A leaky bucket mechanism of the prior art cannot take advantage of the usage pattern described above. Since the single token pool size b must be set according to the largest burst size, the resulting leaky bucket may allow much more bursty traffic than the traffic offered by the user. If the network charges according to the worst case behavior allowed by the leaky bucket the user may be overcharged. If not, the network is susceptible to users who contract for a smaller rate but then take full advantage of the excess allowed by the leaky bucket. Accordingly, in order to better ensure that users stay within negotiated traffic guidelines of a communications network contract, there is a strong need for a policing mechanism which allows a distribution of burst sizes but still retains the simplicity of the leaky bucket mechanism.